Network Decomposition and Maximum Independent Set Part Ⅱ：Application Research

According to the researches on theoretic basis in part I of the paper，the spanning tree algorithms solving the maximum independent set both in even network and in odd network have been developed in this part，part Ⅱ of the paper．The algorithms trans form first the general network into the pair sets network，and then decompose the pair sets network into a series of pair subsets by use of the characteristic of maximum flow passing through the pair sets network．As for the even network，the algorithm requires only one time of trans formation and decomposition，the maximum independent set can be gained without any iteration processes，and the time complexity of the algorithm is within the bound of O(｜V｜^3)．However，as for the odd network，the algorithm consists of two stages．In the first stage，the general odd network is transformed and decomposed into the pseudo-negative envelope graphs and generalized reverse pseudo-negative envelope graphs alternately distributed at first；then the algorithm turns to the second stage，searching for the negative envelope graphs within the pseudo-negative envelope graphs only．Each time as a negative envelope graphhas been found．renew the pair sets network by iteration at once．and then tum back to the first stage．So both stages form a circulation process up to the optimum．Two available methods，the adjusting search and the picking-off search are specially developed to deal with the problems resulted from the odd network．Both of them link up with each other harmoniously and are embedded together in the algorithm．Analysis and study indicate that the time complexity of this algorithm is within the bound of O(｜V｜^5)．     

一种求解Job-Shop调度问题的快速禁忌搜索算法

介绍了一种解决Job-Shop调度最短完工时间的有效的快速禁忌搜索算法,该算法首先利用插入算法构造尽可能好的初始解,然后使用禁忌搜索算法改进当前解,用基准实例进行仿真,实验结果表明该算法是可行的和有效的.     

���ڡ�������������̾�·�㷨

最短径路是网络优化中的一个经典问题，Dijkstra算法被公认为是一种十分有效的最短径路的搜索求解算法．本在研究网络一般结构特点的基础上，发现传统Dijkstra算法在每次迭代过程中都需要搜索所有节点的这一缺陷，通过向搜索节点中引入“度”的信息，提出了基于“度搜索”的改进算法，并根据网络的特点，给出了有向网络和无向网络两种情况下存在“度”差异的算法设计方法；算法的整体结构与Dijkstra保持了一致性，没有算法结构的突变，因而通过修改原有Dijkstra程序和重新设计“度搜索”程序都十分容易实现．该算法提高了最短径路的搜索效率，特别是对稀疏网络，算法效率更为明显，其复杂度小于O(｜V｜^2)．     

列流线偏移描绘自动化

基于图论理论分析了列流图的组成特性,以解决列流线折点自动搜索问题.提出列流线折点搜索算法和列流线偏移描绘算法.采用基于节点信息表绘制列流图.开发了列流图自动生成数据库系统.用实例表明了算法及软件有效性和可行性.     

供水管网多事故关阀方案分析

根据多事故点关阀分析的需求建立了基本网络模型,并建立阀门之间的控制关系,应用广度优先搜索遍历供水管网图,找出多事故点时的关阀集。根据阀门之间的控制关系剔除可不关的阀门,得出最优的关阀方案,并列出了受影响的管段。     

试论发达国家海上救助水平的几个要素及对策

文中通过分析发达国家海上搜救的四要素及我国的各要素现状，结合作者的搜救实践，指出我国海上搜救的不足之处，并提出相关对策。     

A comparison of various algorithms to extract Magic Formula tyre model coefficients for vehicle dynamics simulations

Tyre models are a prerequisite for any vehicle dynamics simulation. Tyre models range from the simplest mathematical models that consider only the cornering stiffness to a complex set of formulae. Among all the steady-state tyre models that are in use today, the Magic Formula tyre model is unique and most popular. Though the Magic Formula tyre model is widely used, obtaining the model coefficients from either the experimental or the simulation data is not straightforward due to its nonlinear nature and the presence of a large number of coefficients. A common procedure used for this extraction is the least-squares minimisation that requires considerable experience for initial guesses. Various researchers have tried different algorithms, namely, gradient and Newton-based methods, differential evolution, artificial neural networks, etc. The issues involved in all these algorithms are setting bounds or constraints, sensitivity of the parameters, the features of the input data such as the number of points, noisy data, experimental procedure used such as slip angle sweep or tyre measurement (TIME) procedure, etc. The extracted Magic Formula coefficients are affected by these variants. This paper highlights the issues that are commonly encountered in obtaining these coefficients with different algorithms, namely, least-squares minimisation using trust region algorithms, Nelder–Mead simplex, pattern search, differential evolution, particle swarm optimisation, cuckoo search, etc. A key observation is that not all the algorithms give the same Magic Formula coefficients for a given data. The nature of the input data and the type of the algorithm decide the set of the Magic Formula tyre model coefficients.     

考虑换乘异质性的城市轨道交通时刻表协同优化模型

在城市轨道交通网络化运营条件下，极易导致换乘站的换乘需求差异过大。为提高列车时刻表与换乘需求的匹配度，本文基于网络中换乘站的空间拓扑结构和换乘需求在时间和方向上的特点，通过构建量化换乘差异的协同度指标，建立以列车同步次数最大化为目标的列车时刻表优化模型，优化轨道交通网络线路间成功衔接次数，提升乘客换乘出行效率。针对提出的混合 整数非线性规划模型，本文设计了一种基于天牛须搜索的粒子群优化算法进行求解，并将模型及算法应用于北京市轨道交通网络进行算例分析。结果表明，所构建的模型能依据换乘需求在空间、时间及方向上的差异，利用协同度分级优化轨道交通路网中列车协同状态；优化后全网列车同步到达次数增加33.86%，乘客平均换乘等待时间减少22.75%；相较于PSO和BAS算法，本文所提的算法具有更好的全局搜索能力和求解效率。本文可有效提高轨道交通换乘效率，为提升城 市轨道交通服务质量提供理论参考。     

不规则物流园区功能区块布局模型与算法

物流园区功能区块的合理布局对于降低物流成本、提高物流作业效率有重要意义.传统的研究主要建立在假定物流园区是矩形的理想情况下,本文基于栅格数据结构,构建了以运输成本最小为目标的不规则物流园区功能区块布局的集合划分模型,并引入了栅格图像矢量化技术,用于提取布局形成后的图像拓扑结构,获得路网信息,然后设计了基于割树技术的变邻域搜索算法进行求解.最后以某物流园区为例,通过MATLAB编程计算得出布局方案,验证了本文模型和算法的有效性.     

A hybrid heuristic strategy for liquefied natural gas inventory routing

As liquefied natural gas (LNG) steadily grows to be a common mode for commercializing natural gas, LNG supply chain optimization is becoming a key technology for gas companies to maintain competitiveness. This paper develops methods for improving the solutions for a previously stated form of an LNG inventory routing problem (LNG-IRP). Motivated by the poor performance of a Dantzig-Wolfe-based decomposition approach for exact solutions, we develop a suite of advanced heuristic techniques and propose a hybrid heuristic strategy aiming to achieve improved solutions in shorter computational time. The heuristics include two phases: the advanced construction phase is based on a rolling time algorithm and a greedy randomized adaptive search procedure (GRASP); and the solution improvement phase is a series of novel MIP-based neighborhood search techniques. The proposed algorithms are evaluated based on a set of realistic large-scale instances seen in recent literature. Extensive computational results indicate that the hybrid heuristic strategy is able to obtain optimal or near optimal feasible solutions substantially faster than commercial optimization software and also the previously proposed heuristic methods.